1. Field of the Invention
The present invention relates to a "theory revision" system that identifies a sequence of revisions which produces a theory with highest accuracy and more particularly, to a system that uses a given set of annotated session transcripts and a given set of possible theory-to-theory revision operators to modify a given theory, encoded as a fault hierarchy, to form a new theory that is optimally accurate.
2. Description of the Prior Art
Many expert systems use a fault hierarchy to propose a repair for a device based on a set of reported symptoms test values. Unfortunately, such systems may return the wrong repair if their underlying hierarchies are incorrect. A theory revision system uses a set, C, of "labeled session transcripts" (each transcript includes answers to the tests posed by the expert system and the correct repair as supplied by a human expert) to modify the incorrect fault hierarchy, to produce a new hierarchy that will be more accurate. Typical revision systems compare the initial hierarchy, KB, with each of its neighbors in N(KB)={KB.sub.k } , where each KB.sub.k is formed from KB by performing a single simple revision, such as deleting a connection between a pair of fault nodes, or altering the order in which some fault nodes are considered. These revision systems will climb from KB to a neighboring KB* .di-elect cons. N(KB) if KB*'s empirical accuracy over C is significantly higher than KB's.
There are many theory revision systems described in the machine learning literature. They all use the same basic idea of using a set of transformations to convert one theory to another. Most of these systems focus on Horn clause knowledge bases or decision trees. These representations are not particularly suited to deployed application systems. By contrast, the Delta system uses a fault hierarchy representation which is widely deployed. Further, the modifications suggested by existing theory revision systems could result in theories which would be rejected by domain experts. By contrast, the Delta system suggests modifications which preserve the structure of the fault hierarchy, and thus are more likely to be acceptable to domain experts. Finally, these systems assume that the training data (i.e., the annotated session transcripts), used to decide which knowledge base is most accurate, will include answers to all relevant tests. This is not realistic in many standard situations, where each training instance includes only the minimal amount of information required to reach an answer, relative to a particular theory. In contrast, the Delta system is designed to evaluate any theory's accuracy, even with incomplete data.